#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>

using namespace std;

//分割回文串VI
//https://leetcode.cn/problems/palindrome-partitioning-iv/submissions/
//class Solution {
//public:
//    bool checkPartitioning(string s) {
//        int n = s.size();
//        //首先找出所有的回文串
//        vector<vector<bool>> vv(n, vector<bool>(n));
//        //i从末尾开始 判断从i-k区间内的字符串是否是回文
//        for (int i = n - 1; i >= 0; --i)
//            for (int k = i; k < n; ++k)
//                if (s[i] == s[k])
//                    vv[i][k] = i + 1 < k ? vv[i + 1][k - 1] : true;
//        //如果字符串长度>2则查看中间i+1和k-1串是否为回文
//
//        for (int i = 1; i < n - 1; ++i) //默认从[0,i] [i+1,k-1] [k,n-1] 三段开始暴力枚举
//            for (int k = i; k < n - 1; ++k)
//                if (vv[0][i - 1] && vv[i][k] && vv[k + 1][n - 1]) return true;
//        //一开始abcbdd三段字符串分别是 a bcbd d 开始从外向内缩
//        return false;
//    }
//};

//分割回文串II
//https://leetcode.cn/problems/palindrome-partitioning-ii/description/
//class Solution {
//public:
//    int minCut(string s) {
//        int n = s.size();
//        vector<vector<bool>> vv(n, vector<bool>(n));
//        for (int i = n - 1; i >= 0; --i)
//            for (int k = i; k < n; ++k)
//                if (s[i] == s[k]) vv[i][k] = i + 1 < k ? vv[i + 1][k - 1] : true;
//
//        vector<int> dp(n, INT_MAX);
//        for (int i = 0; i < n; ++i)
//        {
//            //0-i是否为回文
//            if (vv[0][i]) dp[i] = 0; //为回文则切一刀
//            else//需要分割
//            {
//                for (int k = 1; k <= i; ++k) //检查从0-1 i-k中需要分割多少字串 取最小值
//                    if (vv[k][i]) dp[i] = min(dp[k - 1] + 1, dp[i]);
//                //如果k-i字符串是回文串 只需要判断0-(k-1)需要分割几次即可
//            }
//        }
//        return dp[n - 1];
//    }
//};

//最长回文子序列
//https://leetcode.cn/problems/longest-palindromic-subsequence/description/
// class Solution {
// public:
//     int longestPalindromeSubseq(string s) {
//         int n = s.size();
//         vector<vector<int>> vv(n,vector<int>(n));

//         //如果[i][k]为回文 [i-1]和[k+1]如果相等 那么就能和[i][k]构成回文 回文长度+2
//         //如果[i-1]和[k+1]不相等 则查看[i+1][k] 和 [i][k+1]能否构成回文

//         for(int i = n-1;i>=0;--i)
//         {
//             vv[i][i] = 1; //规避s[i]==s[i]的情况
//             //因为我们会用到[i+1][k-1] 等坐标 用到右边和下面的值
//             //所以需要填写从下往上从左往右填写 - 从上往下就是从右往左扩大遍历区间
//             for(int k = i+1;k<n;++k) //从左往右遍历
//             {
//                 if(s[i] == s[k]) vv[i][k] = vv[i+1][k-1] + 2;
//                 else vv[i][k] = max(vv[i+1][k],vv[i][k-1]);
//             }
//         }

//         return vv[0][n-1];
//     }
// };